#include <iostream>
#include <fstream>
#include <vector>
#include "mgraph.cpp"

using namespace std;

Status topoSort(MGraph G, vector<int> &result);
vector<int> getKeyPath(MGraph net, vector<int> topoArr);

int main(void)
{
	MGraph net(DN);
	Status st;
	int vexnum, arcnum;
	int vex_s, vex_e, vex_w;
	fstream fp;
	vector<int> topoArr, keyPath;
	vector<int>::iterator kp_p;

	fp.open("graph.dat", ios::in);									//打开图的记录文件
	fp >> vexnum >> arcnum;
	for(int i = 1; i <= vexnum; i++)								//按顺序插入顶点
	{
		st = net.InsertVex(i);
		if(st != OK)
			cout << "Error in inserting vertex." << endl;
	}
	for(int i = 0; i <= 14; i++)
	{
		fp >> vex_s >> vex_e >> vex_w;								//读入每条边的始点、终点和边的权值
		st = net.InsertArc(vex_s, vex_e, vex_w);					//在图中插入边
		if(st != OK)
			cout << "Error in inserting arc." << endl;
	}
	fp.close();

	st = topoSort(net, topoArr);									//对图进行拓扑排序，生成拓扑序列
	if(st == OK)
	{
		cout << "The topological sequence of the net is: ";			//输出拓扑序列
		for(vector<int>::iterator i = topoArr.begin(); i != topoArr.end(); i++)
			cout << *i << " ";
		cout << endl;
	}
	else
		return 0;

	keyPath = getKeyPath(net, topoArr);								//根据图和拓扑序列，得出该图的关键路径
	cout << "The key path is: ";									//输出关键路径
	for(kp_p = keyPath.begin(); kp_p != keyPath.end()-1; kp_p++)
		cout << *kp_p << "->";
	cout << *(keyPath.end()) << endl;

	return 0;
}

//拓扑排序函数
Status topoSort(MGraph G, vector<int> &result)
{
	if(G.Graphkind == UDG || G.Graphkind == UDN)					//判断图是否为有向图
		return INFEASIBLE;
	int inDegree[MAX_VERTEX_NUM] = {0}, i, j, vexn = G.vexnum;
	bool visited[MAX_VERTEX_NUM] = {0}, haveZeroInDrgreeVex;
	for(i = 0; i < vexn; i++)
		if(G.arcs[i][i].adj)										//判断图中顶点是否含有环
		{
			cout << "The graph contains a ring." << endl;
			return ERROR;
		}
	for(i = 0; i < vexn; i++)
		for(j = 0; j < vexn; j++)
			if(G.arcs[j][i].adj)
				inDegree[i]++;
	while(vexn)														//进行拓扑排序
	{
		haveZeroInDrgreeVex = false;
		for(i = 0; i < G.vexnum; i++)
			if(inDegree[i] == 0 && !visited[i])						//找到一条入度为0的顶点并将其删去
			{
				haveZeroInDrgreeVex = true;
				result.push_back(G.vexs[i]);
				visited[i] = true;
				for(j = 0; j < G.vexnum; j++)
					if(G.arcs[i][j].adj)
						inDegree[j]--;
				vexn--;
			}
		if(haveZeroInDrgreeVex == false && vexn)					//判断图中是否含有回路
		{
			cout << "The graph has a circuit." << endl;
			return ERROR;
		}

	}
	return OK;
}

//生成关键路径函数
vector<int> getKeyPath(MGraph net, vector<int> topoArr)
{
	vector<int> keyPath;
	vector<int> ES(net.vexnum, 0), LF(net.vexnum, 65535);			//ES为每个顶点的最早开始时间，LF为每个顶点的最晚开始时间
	vector<int>::iterator topo_p, ES_p, LF_p;
	vector<int>::reverse_iterator topo_rp;
	int max, min, i, cur;

	for(topo_p = topoArr.begin()+1; topo_p != topoArr.end(); topo_p++)
	{
		max = 0;
		cur = *topo_p;
		for(i = 0; i < net.vexnum; i++)
			if((net.arcs[i][cur-1].adj) && (net.arcs[i][cur-1].adj + ES[i]) > max)
				max = net.arcs[i][cur-1].adj + ES[i];
		ES[cur-1] = max;											//按照拓扑序列依次计算每个顶点的最早开始时间
	}

	LF[cur-1] = ES[cur-1];											//最后一个顶点的最晚开始时间等于其最早开始时间
	for(topo_rp = topoArr.rbegin()+1; topo_rp != topoArr.rend(); topo_rp++)
	{
		min = 65535;
		cur = *topo_rp;
		for(i = 0; i < net.vexnum; i++)
			if((net.arcs[cur-1][i].adj) && (LF[i] - net.arcs[cur-1][i].adj) < min)
				min = LF[i] - net.arcs[cur-1][i].adj;
		LF[cur-1] = min;											//按照拓扑序列的逆序列依次计算每个顶点的最晚开始时间
	}

	cout << "num\tES\tLF" << endl;									//输出每个顶点的最早和最晚开始时间
	for(topo_p = topoArr.begin(); topo_p != topoArr.end(); topo_p++)
		cout << *topo_p << "\t" << ES[*topo_p-1] << "\t" << LF[*topo_p-1] << endl;

	for(topo_p = topoArr.begin(); topo_p != topoArr.end(); topo_p++)
		if(ES[*topo_p-1] == LF[*topo_p-1])							//如果一个顶点的最早开始时间与最晚开始时间相同，则它为关键路径的一个结点
			keyPath.push_back(*topo_p);

	return keyPath;
}